// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-22 15:01
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.Graph.Dijkstra;

//Dijkstra算法

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

@SuppressWarnings({"ALL"})
public class Dijkstra {
    public static void main(String[] args) {
        String fileName = "D:\\Java_idea\\AlgorithmsLearn\\src\\com\\DataStruct\\Graph\\Dijkstra\\demo.txt";
        Character startPoint = 'A';
        Character endPoint = 'E';
        File file = new File(fileName);
        BufferedReader reader = null;
        String tempString = null;
        /*-----图的节点和节点对应的出边-----*/
        // 使用HashMap构建图的邻接链表
        HashMap<Character, ArrayList<TwoTuple<Character, Integer>>> connects = new HashMap<>();
        /*-----初始化边数据节点信息，将已知的信息方法connects集合进行存储-----*/
        try {
            reader = new BufferedReader(new FileReader(file));
            /*-----文件读取方法-----*/
            while (null != (tempString = reader.readLine())) {
                String[] tempStrSplit = tempString.split(" ");
                TwoTuple<Character, Integer> tempTwoTuple = new TwoTuple<>(
                        // 边的目标节点和边的权值
                        tempStrSplit[1].charAt(0), Integer.parseInt(tempStrSplit[2]));
                /*-----连接集合已经含有该点出边-----*/
                if (connects.containsKey(tempStrSplit[0].charAt(0))) {
                    ArrayList<TwoTuple<Character, Integer>> tempArr = connects.get(tempStrSplit[0].charAt(0));
                    // 将边信息加入邻接链表中
                    tempArr.add(tempTwoTuple);
                    //connects.replace(tempStrSplit[0].charAt(0), tempArr);
                    connects.put(tempStrSplit[0].charAt(0), tempArr);
                } else { //连接集合未含该点出边
                    ArrayList<TwoTuple<Character, Integer>> tempArr = new ArrayList<>();
                    tempArr.add(tempTwoTuple);
                    connects.put(tempStrSplit[0].charAt(0), tempArr);
                }
            }
            reader.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
        //获得最短路径结果
        TwoTuple<Character[], Integer> res = DijkstraMethod(connects, startPoint, endPoint);
        //打印最短路径结果
        System.out.println("Path :");
        for (int i = 0; i <= res.fst.length - 1; i++) {
            System.out.print(res.fst[i] + " -> ");
        }
        System.out.println("Length :");
        System.out.println(res.snd);
    }

    /**
     * Dijikstra算法核心代码
     *
     * @param source:     邻接链表存储的图信息
     * @param startPoint: 起点
     * @param endPoint:   终点
     * @return
     */
    public static TwoTuple<Character[], Integer> DijkstraMethod(
            HashMap<Character, ArrayList<TwoTuple<Character, Integer>>> source, Character startPoint, Character endPoint) {
        /*-----未访问节点-----*/
        ArrayList<Character> open = new ArrayList<>();
        /*-----已访问节点-----*/
        ArrayList<Character> closed = new ArrayList<>();
        /*-----顶点集合-----*/
        HashSet<Character> points = new HashSet<>();
        //获得所有点集，所有元素寻找，set中不存在重复数据
        source.forEach((k, v) -> {
            points.add(k);
            v.forEach(x -> {
                points.add(x.fst);
            });
        });
        Character[] allPoints = new Character[points.size()];
        Character[] fatherPoints = new Character[points.size()];
        int[] dists = new int[points.size()];
        int[] distRes = new int[points.size()];
        int k = 0;
        //将点集转化为字符数组形式
        /*-----数据初始化-----*/
        for (Iterator<Character> iterator = points.iterator(); iterator.hasNext(); ) {
            Character thisChar = iterator.next();
            //添加开集
            open.add(thisChar);
            //初始化节点数组
            allPoints[k] = thisChar;
            //初始化父节点数组
            fatherPoints[k] = thisChar;
            //初始化距离数组
            dists[k] = Integer.MAX_VALUE;
            k++;
        }
        /*-----寻找起始节点索引-----*/
        k = findIndex(allPoints, startPoint);
        dists[k] = 0;
        int tempIndex = 0;
        //开集有终点则一直继续寻找轨迹
        while (open.contains(endPoint)) {
            //找到当前距离最小节点
            k = findMinNumIndex(dists);
            //从开集中移除
            open.remove(allPoints[k]);
            //加入闭集
            closed.add(allPoints[k]);
            //将最终距离存储
            distRes[k] = dists[k];
            //距离置为-1，不参与最小值判断
            dists[k] = -1;
            //若终点被移除，则停止迭代
            if (allPoints[k].equals(endPoint)) {
                break;
            }
            ArrayList<TwoTuple<Character, Integer>> thisPointConnect = source.get(allPoints[k]);
            for (int i = 0; i < thisPointConnect.size(); i++) {
                // 在加入新的节点之后，更新所有可能变化路径的节点
                tempIndex = findIndex(allPoints, thisPointConnect.get(i).fst);
                //符合更新条件，从当前节点到目标节点的路径长度小于原来的路径
                if (distRes[k] + thisPointConnect.get(i).snd < dists[tempIndex]) {
                    fatherPoints[tempIndex] = allPoints[k];
                    dists[tempIndex] = distRes[k] + thisPointConnect.get(i).snd;
                }
            }
        }
        //输出路径和距离
        k = findIndex(allPoints, endPoint);
        ArrayList<Character> output = new ArrayList<>();
        output.add(endPoint);
        /*-----根据路径数组获取整个路径-----*/
        while (!allPoints[k].equals(startPoint)) {
            output.add(fatherPoints[k]);
            k = findIndex(allPoints, fatherPoints[k]);
        }
        Character[] outChars = new Character[output.size()];
        for (int i = 0; i < output.size(); i++) {
            outChars[i] = output.get(output.size() - 1 - i);
        }
        k = findIndex(allPoints, endPoint);
        TwoTuple<Character[], Integer> res = new TwoTuple<>(outChars, distRes[k]);
        return res;
    }

    /**
     * 寻找索引
     *
     * @param chars
     * @param charOne
     * @return
     */
    public static int findIndex(Character[] chars, Character charOne) {
        for (int i = 0; i < chars.length; i++) {
            if (chars[i].equals(charOne)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回边集合中距离最短的边的索引
     *
     * @param ints
     * @return
     */
    public static int findMinNumIndex(int[] ints) {
        int minNum = Integer.MAX_VALUE;
        int minNumIndex = 0;
        for (int i = 0; i < ints.length; i++) {
            // 免去了距离为-1的节点，因为该节点已经加入到图中
            if (ints[i] < minNum && ints[i] >= 0) {
                minNum = ints[i];
                minNumIndex = i;
            }
        }
        return minNumIndex;
    }
}

/**
 * 泛型的使用经典案列
 *
 * @param <K> 边的目标节点
 * @param <V> 边的权值 或者 路径长度
 */
class TwoTuple<K, V> {
    public final K fst;
    public final V snd;

    TwoTuple(K k, V v) {
        fst = k;
        snd = v;
    }
}
